package 算法回顾;

import 我的JDK基础数据结构.ArrayList.ArrayList;

import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-09-12
 **/

public class JZ11旋转数组的最小数字 {

    /**
     * 有点啰嗦的解法
     */
    public int minArray(int[] numbers) {

        if (numbers.length == 0) {
            return -1;
        }

        int left = 0;
        int right = numbers.length-1;

        while (left < right) {

            // 最左小于最右,最左直接是答案
            if (numbers[left] < numbers[right]) {
                return numbers[left];
            }

            // 最左等于最右,right-- 因为升序,切记right--非left++
            if (numbers[left] == numbers[right]) {
                right--;
                continue;
            }

            // 最左大于最右,找中间值,更新指针
            int mid = (right - left) / 2 + left;
            // 中间大于最右,最小
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
                continue;
            }
            // 等于
            if (numbers[mid] == numbers[right]) {
                right--;
                continue;
            }
            // 中间小于最右
            right = mid;

        }

        return numbers[left];
    }

    public int minArrayGood(int[] numbers) {

        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (numbers[left] < numbers[right]) {
                return numbers[left];
            }
            // 右范围一定有序
            if (numbers[right] > numbers[mid]) {
                right = mid;
            } else if(numbers[right] < numbers[mid]) {
                left = mid + 1;
            } else {
                right--;
            }
        }

        return numbers[left];
    }

    public static void main(String[] args) {
        JZ11旋转数组的最小数字 n = new JZ11旋转数组的最小数字();
        int[] arr = {2,2,2,0,2};
        int result = n.minArrayGood(arr);
        System.out.println(result);
    }

}
